import java.util.*;

/**
 * @author HuanyuZhou
 * @date 2020/12/2 11:34
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean onlyOnce = solution.isOnlyOnce(new int[]{1,3, 4, 5});
//        System.out.println(onlyOnce);
        GoLdMine[] arr = new GoLdMine[5];
        arr[1] = new GoLdMine(500,5);
        arr[2] = new GoLdMine(200,3);
        arr[3] = new GoLdMine(100,1);
        arr[4] = new GoLdMine(700,6);
        arr[0] = new GoLdMine(50,2);
        List<GoLdMine> maxVlue = solution.getMaxVlue(arr, 11);
        for (GoLdMine goLdMine : maxVlue) {
            System.out.println(goLdMine);
        }

    }


    //查询数字是否只出现一次
    public boolean isOnlyOnce(int[] arr){
        //用set查询是否有过。
        Set<Integer> set  = new HashSet<>();
        for (int i : arr) {
            //有则返回false
            if(set.contains(i)){
                return false;
            }
            set.add(i);
        }
        //循环完毕。都没有。返回true
        return true;
    }

    //动态规划
    public List<GoLdMine>  getMaxVlue(GoLdMine[] goLdMines,int workNums) {
        //生成一个二位数组，col有工人总数+1，row金矿总数+1
        List<GoLdMine>[][] dp = new ArrayList[goLdMines.length+1][workNums+1];
        //初始化。在0个金矿时，所有都为空的arrayList
        for (int i = 0; i < workNums+1; i++) {
            dp[0][i] = new ArrayList<>();
        }
        //遍历
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                int nums = goLdMines[i - 1].getNums();
                List<GoLdMine> list = new ArrayList<>();
                //如果工人数少于金矿，就取上面的值
                if(j < nums){
                    list.addAll(dp[i-1][j]);
                    dp[i][j] = list;
                    continue;
                }
                //开始计算不加该金矿和加了该金矿谁得重量大
                int prev = 0;
                int now = 0;
                for (GoLdMine goLdMine : dp[i - 1][j]) {
                    prev+=goLdMine.getWeight();
                }
                //找上层减掉该金矿所需要得人数得到得重量
                for (GoLdMine goLdMine : dp[i - 1][j - nums]) {
                    now+=goLdMine.getWeight();
                }
                now +=goLdMines[i-1].getWeight();
                //如果加了这个金矿重量大，就加入上层+该金矿
                if(now > prev){
                    list.addAll(dp[i-1][j-nums]);
                    list.add(goLdMines[i - 1]);
                    dp[i][j] = list;
                //如果没有，就保存上层得金矿方案
                }else{
                    list.addAll(dp[i-1][j]);
                    dp[i][j] = list;
                }
            }
        }

        //返回最右下角得值
        return dp[goLdMines.length][workNums];
    }
}
